package org.liaohailong.helloworld.practicemiddle;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: liaohailong
 * Date: 2021/7/20
 * Time: 22:00
 * Description: 中级算法 - 回溯
 **/
public class RecallPractice {

    // LC 电话号码的字母组合
    public List<String> letterCombinations(String digits) {
        final char[][] dictionaries = new char[][]{
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'},
        };

        // 构建树
        char[] arr = digits.toCharArray();
        // BFS
        ArrayList<ArrayList<Character>> tree = new ArrayList<>();
        for (char c : arr) {
            int index = Character.digit(c, 10) - 2;
            ArrayList<Character> words = new ArrayList<>();
            for (char word : dictionaries[index]) {
                words.add(word);
            }
            tree.add(words);
        }
        List<String> result = new LinkedList<>();
        _letterCombinations(tree, 0, new LinkedList<>(), result);
        return result;
    }

    private void _letterCombinations(ArrayList<ArrayList<Character>> tree,
                                     int depth, LinkedList<Character> path,
                                     List<String> result) {
        if (depth >= tree.size()) {
            if (path.size() > 0) result.add(makeStr(path));
            return;
        }
        ArrayList<Character> level = tree.get(depth);
        for (Character c : level) {
            path.addLast(c);
            _letterCombinations(tree, depth + 1, path, result);
            path.removeLast();
        }
    }

    private String makeStr(LinkedList<Character> path) {
        StringBuilder sb = new StringBuilder();
        for (Character c : path) sb.append(c);
        return sb.toString();
    }


    // LC 括号生成
    public List<String> generateParenthesis(int n) {
//        输入：n = 3
//        输出：["((()))","(()())","(())()","()(())","()()()"]

//        输入：n = 1
//        输出：["()"]

        // dfs
        List<String> result = new LinkedList<>();
        LinkedList<Character> path = new LinkedList<>();
        _generateParenthesis(path, 0, 0, n, result);
        return result;
    }

    private void _generateParenthesis(LinkedList<Character> path,
                                      int leftCount,
                                      int rightCount,
                                      int maxCount,
                                      List<String> result) {
        if (rightCount > leftCount) return; // 无效的括号组合
        if (path.size() >= maxCount * 2) {
            result.add(makeStr(path));
            return;
        }

        if (leftCount < maxCount) {
            path.addLast('(');
            _generateParenthesis(path, leftCount + 1, rightCount, maxCount, result);
            path.pollLast();
        }

        path.addLast(')');
        _generateParenthesis(path, leftCount, rightCount + 1, maxCount, result);
        path.pollLast();
    }


    // LC 全排列
    public List<List<Integer>> permute(int[] nums) {
//        输入：nums = [1,2,3]
//        输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        boolean[] record = new boolean[nums.length];
        _permute(nums, 0, nums.length - 1, record, path, result);
        return result;
    }

    private void _permute(int[] nums, int start, int end,
                          boolean[] record,
                          LinkedList<Integer> path,
                          List<List<Integer>> result) {
        if (path.size() >= nums.length) {
            List<Integer> list = new LinkedList<>(path);
            result.add(list);
            return;
        }

        for (int i = start; i <= end; i++) {
            if (record[i]) continue;
            path.addLast(nums[i]);
            record[i] = true;
            _permute(nums, start, end, record, path, result);
            path.pollLast();
            record[i] = false;
        }
    }

    // LC 子集
//    public List<List<Integer>> subsets(int[] nums) {
////        输入：nums = [1,2,3]
////        输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//
//        LinkedList<Integer> path = new LinkedList<>();
//        HashSet<String> set = new HashSet<>();
//        List<List<Integer>> result = new LinkedList<>();
//        result.add(new LinkedList<>());
//        boolean[] record = new boolean[nums.length];
//        _subsets(nums, record, path, set, result);
//        return result;
//    }
//
//    private void _subsets(int[] nums,
//                          boolean[] record,
//                          LinkedList<Integer> path,
//                          HashSet<String> set,
//                          List<List<Integer>> result) {
//        if (path.size() >= nums.length) {
//            String key = makeStrBySort(path);
//            if (!set.contains(key)) {
//                set.add(key);
//                result.add(new ArrayList<>(path));
//            }
//            return;
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            if (record[i]) continue;
//            record[i] = true;
//            path.addLast(nums[i]);
//            String key = makeStrBySort(path);
//            if (!set.contains(key)) {
//                set.add(key);
//                result.add(new ArrayList<>(path));
//                _subsets(nums, record, path, set, result);
//            }
//            path.pollLast();
//            record[i] = false;
//        }
//    }
//
//    private String makeStrBySort(LinkedList<Integer> path) {
//        Integer[] integers = path.toArray(new Integer[]{});
//        Arrays.sort(integers);
//        StringBuilder sb = new StringBuilder();
//        for (Integer val : integers) sb.append(val);
//        return sb.toString();
//    }

    // LC 子集
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), nums, 0);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> list, int[] nums, int index) {
        List<Integer> myli = new ArrayList<>(list);
        res.add(myli);
        for (int i = index; i < nums.length; i++) {
            myli.add(nums[i]);
            backtrack(res, myli, nums, i + 1);
            myli.remove(myli.size() - 1);
        }
    }


    // LC 单词搜索
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                boolean[][] visited = new boolean[board.length][board[i].length];
                boolean exist = _exist(board, i, j, 0, visited, words);
                if (exist) return true;
            }
        }
        return false;
    }

    private boolean _exist(char[][] board, int i, int j, int count,
                           boolean[][] visited,
                           char[] words) {
        if (i >= board.length || i < 0 || j >= board[i].length || j < 0) {
            // 无路可走，检查结果
            return count == words.length;
        }
        // words吻合，返回true
        if (count == words.length) return true;

        // 判断i,j是否已经访问过
        boolean isVisited = visited[i][j];
        if (!isVisited) {
            visited[i][j] = true;
            char c = board[i][j];
            char target = words[count];
            // 顺序比对单词是否一致
            if (c == target) {
                count++;
                // 上路
                boolean up = _exist(board, i - 1, j, count, visited, words);
                if (up) return true;
                // 下路
                boolean down = _exist(board, i + 1, j, count, visited, words);
                if (down) return true;
                // 左路
                boolean left = _exist(board, i, j - 1, count, visited, words);
                if (left) return true;
                // 右路
                boolean right = _exist(board, i, j + 1, count, visited, words);
                if (right) return true;
            }
            visited[i][j] = false;
            return false;
        }
        return count == words.length;
    }

}
